{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Author: OMKAR PATHAK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is an Array?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Array is a data structure used to store homogeneous elements at contiguous locations.\n",
    "* One memory block is allocated for the entire array to hold the elements of the array. The array elements can be accessed in constant time by using the index of the particular element as the subscript."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Properties of Arrays:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Arrays stores similar data types. That is, array can hold data of same data type values. This is one of the limitations of arrays compared to other data structures.\n",
    "\n",
    "* Each value stored, in an array, is known as an element and all elements are indexed. The first element added, by default, gets 0 index. That is, the 5th element added gets an index number of 4.\n",
    "\n",
    "* Elements can be retrieved by their index number. (__random access__)\n",
    "\n",
    "* Array elements are stored in contiguous (continuous) memory locations.\n",
    "\n",
    "* One array name can represent multiple values. Array is the easiest way to store a large quantity of data of same data types. For example, to store the salary of 100 employees, it is required to declare 100 variables. But with arrays, with one array name all the 100 employees salaries can be stored.\n",
    "\n",
    "* At the time of creation itself, array size should be declared (array initialization does not require size)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Arrays in Python:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python does not have a native support for arrays, but has a more generic data structure called LIST. List provides all the options as array with more functionality.\n",
    "But with few tweaks we can implement Array data structure in Python.\n",
    "We will be seeing how to do this."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Creating an array:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 0 0 0 0 0 0 0 0\n"
     ]
    }
   ],
   "source": [
    "class Array(object):\n",
    "    ''' sizeOfArray: denotes the total size of the array to be initialized\n",
    "       arrayType: denotes the data type of the array(as all the elements of the array have same data type)\n",
    "       arrayItems: values at each position of array\n",
    "    '''\n",
    "    def __init__(self, sizeOfArray, arrayType = int):\n",
    "        self.sizeOfArray = len(list(map(arrayType, range(sizeOfArray))))\n",
    "        self.arrayItems =[arrayType(0)] * sizeOfArray    # initialize array with zeroes\n",
    "        \n",
    "    def __str__(self):\n",
    "            return ' '.join([str(i) for i in self.arrayItems])\n",
    "            \n",
    "    # function for search\n",
    "    def search(self, keyToSearch):\n",
    "        for i in range(self.sizeOfArray):\n",
    "            if (self.arrayItems[i] == keyToSearch):    # brute-forcing\n",
    "                return i     # index at which element/ key was found\n",
    "            \n",
    "        return -1          # if key not found, return -1\n",
    "    \n",
    "    # function for inserting an element\n",
    "    def insert(self, keyToInsert, position):\n",
    "        if(self.sizeOfArray > position):\n",
    "            for i in range(self.sizeOfArray - 2, position - 1, -1):\n",
    "                self.arrayItems[i + 1] = self.arrayItems[i]\n",
    "            self.arrayItems[position] = keyToInsert\n",
    "        else:\n",
    "            print('Array size is:', self.sizeOfArray)\n",
    "            \n",
    "    # function to delete an element\n",
    "    def delete(self, keyToDelete, position):\n",
    "        if(self.sizeOfArray > position):\n",
    "            for i in range(position, self.sizeOfArray - 1):\n",
    "                self.arrayItems[i] = self.arrayItems[i + 1]\n",
    "        else:\n",
    "            print('Array size is:', self.sizeOfArray)\n",
    "    \n",
    "a = Array(10, int)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Common array operations:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Search\n",
    "* Insert\n",
    "* Delete\n",
    "\n",
    "__Time complexity__:\n",
    "\n",
    "* Search: O(n)\n",
    "* Insert: O(n)\n",
    "* Delete: O(n)\n",
    "* Indexing: O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Search Operation on Array:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element found at: 0\n"
     ]
    }
   ],
   "source": [
    "a = Array(10, int)\n",
    "index = a.search(0)\n",
    "print('Element found at:', index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Insert Operation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 1 2 3 0 0 0 0 0\n"
     ]
    }
   ],
   "source": [
    "a = Array(10, int)\n",
    "a.insert(1, 2)\n",
    "a.insert(2,3)\n",
    "a.insert(3,4)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Delete Operation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 1 2 0 0 0 0 0 0\n",
      "Element found at: 2\n"
     ]
    }
   ],
   "source": [
    "a = Array(10, int)\n",
    "a.insert(1, 2)\n",
    "a.insert(2,3)\n",
    "a.insert(3,4)\n",
    "a.delete(3, 4)\n",
    "print(a)\n",
    "index = a.search(1)\n",
    "print('Element found at:',index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### These were the basics of how to implement Array using Python. Now we will see how to use Python built-in module 'array'.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Syntax: array(dataType, valueList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The new created array is : 1 2 3 4 5 \n",
      "The appended array is : 1 2 3 4 5 6 \n",
      "The array after insertion is : 1 2 5 3 4 5 6 \n",
      "The array after deletion is : 2 5 3 4 5 6 "
     ]
    }
   ],
   "source": [
    "# importing 'array' module \n",
    "import array\n",
    "\n",
    "# initializing array\n",
    "arr = array.array('i', [1, 2, 3, 4, 5])     # initialize array with integers ('i')\n",
    "\n",
    "# printing original array\n",
    "print (\"The new created array is : \",end=\"\")\n",
    "for i in range (0, 5):\n",
    "    print (arr[i], end=\" \")\n",
    "\n",
    "# using append() to insert new value at end\n",
    "arr.append(6);\n",
    "\n",
    "# printing appended array\n",
    "print (\"\\nThe appended array is : \", end=\"\")\n",
    "for i in range (0, 6):\n",
    "    print (arr[i], end=\" \")\n",
    "\n",
    "# using insert() to insert value at specific position\n",
    "# inserts 5 at 2nd position\n",
    "arr.insert(2, 5)\n",
    "\n",
    "# printing array after insertion\n",
    "print (\"\\nThe array after insertion is : \", end=\"\")\n",
    "for i in range (0, 7):\n",
    "    print (arr[i], end=\" \")\n",
    "    \n",
    "arr.remove(1)\n",
    "\n",
    "# deleting a  value from array\n",
    "print (\"\\nThe array after deletion is : \", end=\"\")\n",
    "for i in range (0, 6):\n",
    "    print (arr[i], end=\" \")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Disadvantages of Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* __Fixed size__: The size of the array is static (specify the array size before using it, this can be overcome using Dynamic Arrays).\n",
    "* __One block allocation__: To allocate the array itself at the beginning, sometimes it may not be possible to get the memory for the complete array (if the array size is big).\n",
    "* __Complex position-based insertion__: To insert an element at a given position, we may need to shift the existing elements. This will create a position for us to insert the new element at the desired position. If the position at which we want to add an element is at the beginning, then the shifting operation is more expensive ."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}